1. Field
The present invention lies in the field of algorithms and processing methods for graph databases. In particular, the present invention relates to a method for finding the k shortest paths between two vertices in a graph database.
2. Description of the Related Art
Shortest path analysis is a fundamental graph processing operation. It computes either the shortest path from a single source vertex to every other vertex in the graph, the shortest path between a specified pair of vertices, or the shortest path between every pair of graph vertices. Shortest path is normally computed on a directed, weighted graph where the edge weights can be equal or different and positive or negative (if negative loops do not exist). Shortest path analysis can also be carried out in an undirected graph. Algorithms exist for finding the shortest path between two vertices in a graph database, for example, the Dijkstra algorithm presents good theoretical and practical results.
In practice, finding the shortest path is not always the most useful operation, and applications may, in fact, require discovery of the second shortest, third shortest, etc. paths. For example, there may be scenarios in which the shortest path is not always ideal or available. Therefore, operations exist for finding the k-shortest paths.
An existing k-shortest path algorithm is the Yen algorithm. The Yen algorithm first computes the shortest path P using, for example, the Dijkstra algorithm. It then iteratively breaks away from P, by defining a branch point and replacing an edge on P with a sub-optimal edge. The final top ranking K alternative paths are then considered the solution to the problem.
Due to the nature of the Yen algorithm (maintaining centralized queue of next vertex to be processed, K iteration is based on the status of K−1 iteration, monitoring global variables, etc.) it is difficult to parallelize and hence is computationally expensive. System performance bottlenecks can arise.